package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/merge-in-between-linked-lists/'>合并两个链表(Merge In Between Linked Lists)</a>
 * <p>给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。</p>
 * <p>请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
 *      输出：[0,1,2,1000000,1000001,1000002,5]
 *      解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
 *
 * 示例 2：
 *      输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
 *      输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
 *      解释：上图中蓝色的边和节点为答案链表。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>3 <= list1.length <= 10^4</li>
 *      <li>1 <= a <= b < list1.length - 1</li>
 *      <li>1 <= list2.length <= 10^4</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/8 18:33
 */
public class LC1669MergeInBetween_M {
    static class Solution {
        public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
            // 找到 a位置 的前一个节点
            ListNode currNode = list1;
            for (int i = 1; i < a; i++) {
                currNode = currNode.next;
            }
            // 记录 a 位置的前一个节点
            ListNode prevA = currNode;
            // 找到 b 的下一个节点。
            for (int i = a; i < b + 2; i++) {
                currNode = currNode.next;
            }
            prevA.next = list2;
            while (list2.next != null) {
                list2 = list2.next;
            }
            list2.next = currNode;
            return list1;
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.mergeInBetween(
                Generator.create(0, 1, 2, 3, 4, 5, 6),
                2,
                5,
                Generator.create(1000000, 1000001, 1000002, 1000003, 1000004)
        ));
    }
}
